//给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。 
//示例：
//
// 
//给定有序数组: [-10,-3,0,5,9],
//
//一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
//
//          0 
//         / \ 
//       -3   9 
//       /   / 
//     -10  5 
// 
//
// Related Topics 树 二叉搜索树 数组 分治 二叉树 👍 163 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-07-01 22:27:06
 * @description 面试题 04.02.最小高度树
 */
public class MinimumHeightTreeLcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 MinimumHeightTreeLcci fun=new MinimumHeightTreeLcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

//  Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(0,nums.length-1,nums);
    }
	private TreeNode dfs(int l,int r,int[] nums){
        if(l>r) return null;
        int m=(l+r)/2;
        TreeNode node1=new TreeNode(nums[m]);
        node1.left=dfs(l,m-1,nums);
        node1.right=dfs(m+1,r,nums);
        return node1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
